[回溯算法]python解决N皇后问题(20行代码)

2023-08-17 20:46| 来源: 网络整理| 查看: 265

如果读者对于回溯算法思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【回溯算法】详解》，很详细的介绍了回溯算法求解思路及方法，有利于你更好的学习回溯算法。

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

注：下图为 8 皇后问题的一种解法。

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

N皇后问题.png

示例1

输入：4 输出：解法 1： [".Q..", "...Q", "Q...", "..Q."],

解法 2：["..Q.", "Q...", "...Q", ".Q.."] 解释: 4 皇后问题存在两个不同的解法。

问题分析

直接套用《算法之【回溯算法】详解》中的回溯算法基本步骤以及回溯算法的通用框架模板。

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def backtrack(board, row): if row >= n: # 此处是将每一行转换为题目要求的字符串形式,如"..Q."代表一行 cur_res = [''.join(row) for row in board] res.append(cur_res) #保存结果 return for i in range(n): if isValid(row, i, board): #isValid用于判断该位置是否合法，能够放置皇后 board[row][i] = 'Q' #放置皇后 backtrack(board, row+1) # row+1进入下一行 board[row][i] = '.' #回溯 res = [] board = [['.'] * n for _ in range(n)] # 初始化棋盘 backtrack(board, 0) # row从0开始 return res

1. 状态变量为行：row,每次在当前行选择完一个可以放置的皇后位置后进入下一行row+1;

2. 递归结束条件:当row>=n时，row从0开始，表示前n-1所有行的皇后均已放置完成，将结果添加到res中。

if row >= n: # 此处是将每一行转换为题目要求的字符串形式,如"..Q."代表一行 cur_res = [''.join(row) for row in board] res.append(cur_res) return

3. 可选择的列表：每一行能够选择的位置为0到n-1，但是该位置是否能够被选择，需要满足皇后彼此不能相互攻击的条件。

此处判断是否能够相互攻击即判断当前位置(row, col)所在的列，右斜线方向即左斜线方向是否已经有皇后存在，如果有的话，则当前位置不能再放皇后。

判断是否有冲突的方式有两种：

方法一：直接通过循环判断

def isVaild(board,row, col): #判断同一列是否冲突 for i in range(len(board)): if board[i][col] == 'Q': return False # 判断左上角是否冲突 i = row -1 j = col -1 while i>=0 and j>=0: if board[i][j] == 'Q': return False i -= 1 j -= 1 # 判断右斜线方向是否冲突 i = row - 1 j = col + 1 while i>=0 and j < len(board): if board[i][j] == 'Q': return False i -= 1 j += 1 return True

方法二: 左斜线:同一斜线每个点row-col恒定; 右斜线：同一斜线每个点row+col恒定

左斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)和 (3,3)在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

左斜.png

右斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

右斜.png

下面我们主要使用第二种方法来进行判断所放置的位置是否合法。

def isValid(row, col): # 判断所放置的位置是否合法 for i in range(row): for j in range(n): # 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等 # 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等 if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col): return False return True 最终代码 class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def isValid(row, col): # 判断所放置的位置是否合法 for i in range(row): for j in range(n): if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col): return False return True def backtrack(board, row): if row >= n: cur_res = [''.join(row) for row in board] res.append(cur_res) return for i in range(n): if isValid(row, i, board): board[row][i] = 'Q' backtrack(board, row+1) board[row][i] = '.' res = [] board = [['.'] * n for _ in range(n)] backtrack(board,0) return res

代码优化：通过集合记录之前放置过元素的正向对角线，负向对角线，及列，判断当前点是否在集合中，在的话说明不满足要求，这种判断方式速度更快。

def solveNQueens(self, n: int) -> List[List[str]]: def isValid(row, col): # 如果该点所对应的右斜线或左斜线或列已经放置了皇后则放回Fasle if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash: return False return True def backtrack(board, row): if row >= n: cur_res = [''.join(row) for row in board] res.append(cur_res) return for col in range(n): if isValid(row, col, board): board[row][col] = 'Q' pie_hash.add(row + col) na_hash.add(row - col) col_hash.add(col) backtrack(board, row+1) board[row][col] = '.' pie_hash.remove(row + col) na_hash.remove(row-col) col_hash.remove(col) res = [] board = [['.'] * n for _ in range(n)] pie_hash = set() # 记录放置了皇后的右斜线 na_hash = set() # 记录放置了皇后的左斜线 col_hash = set() # 记录放置了皇后的列 backtrack(board,0) return res

后续会继续更新关于回溯算法的相关题解，欢迎持续关注！如果喜欢作者，欢迎点赞、收藏及关注，谢谢！

【本文地址】

公司简介

联系我们